package com.itheima.algorithm.recursion_multi;

import java.util.LinkedList;

/**
 * @author tantao
 * @version 1.0
 * @description: 汉诺塔
 * @date 2025/8/21 14:28
 */
public class E02HanoiTower01 {
    static LinkedList<Integer> a = new LinkedList<>();
    static LinkedList<Integer> b = new LinkedList<>();
    static LinkedList<Integer> c = new LinkedList<>();

    //初始化
    static void init(int n) {
        for (int i = n; i >= 1; i--) {
            a.addLast(i);
        }
    }

    public static void main(String[] args) {
        init(64);
        move(64, a, b, c);
    }

    private static void print() {
        System.out.println("----------------");
        System.out.println("a:" + a);
        System.out.println("b:" + b);
        System.out.println("c:" + c);
    }


    /**
     * 分析：
     * 一个圆盘:
     *  1: a->c
     * 两个圆盘:
     *  1：a->b
     *  2: a->c
     *  1: b->c
     *  三个圆盘:
     *  1.2: a->b
     *  3: a->c
     *  1.2:b->c
     *  四个圆盘
     *  1.2.3: a->b
     *  4: a->c
     *  1.2.3:b->c
     *  通用公式：n 个圆盘:
     *  1.2.3.4...n-1: a->b
     *  n: a->c
     *  1.2.3.4...n-1:b->c
     *
     */

    /** O(2^n)
     * @param n 圆盘个数
     * @param a 原
     * @param b 借助
     * @param c 目标
     */
    private static void move(int n,
                             LinkedList<Integer> a,
                             LinkedList<Integer> b,
                             LinkedList<Integer> c) {
        if (n == 0) {
            return;
        }
        //将n-1，从a->b移动
        move(n - 1, a, c, b);
        //将n，从a->c移动
        c.addLast(a.removeLast());
        print();
        //将n-1，从b->c移动
        move(n - 1, b, a, c);

    }
}
